package com.example.algorithms.sort;

/**
 * @Author Zhang Jie
 * @Date 9/28/20
 * @Version 1.0
 */

import java.util.Arrays;

/**
 * 快速排序
 *
 * 不是一个稳定的排序算法，因为涉及到交换操作
 * 原地排序的算法
 * 最坏的时间复杂度为O(n^2),最好的时间复杂度是O(nlogn),平均时间复杂度为O(nlogn)
 * 使用递归来实现
 * 处理过程是由上到下，先分区，再处理子问题
 *
 * @author jane
 */
public class QuickSort {

    /**
     * 从小到大排序
     * @param arr
     * @return
     */
    public static int[] sortUp(int[] arr){
        if(arr==null||arr.length<2){
            return arr;
        }

        _sortUp(arr,0,arr.length-1);

        return arr;
    }
    public static int[] sortUp(int[] arr, int len){
        if(arr==null || len<2){
            return arr;
        }
        _sortUp(arr,0,len-1);
        return arr;
    }

    /**
     * 主要是要把基础值放到数组中间,左边放小于它的值,右边放大于它的值
     */
    private static int[] _sortUp(int[]arr, int begin, int end){

        if(begin>=end){
            return arr;
        }

        int cur=arr[end];

        //第一种: i和j都从前往后
        int i=begin;
        int j=begin;

        while(j<=end){
            if(arr[j]<=cur){
                if(i!=j){
                    int temp=arr[i];
                    arr[i]=arr[j];
                    arr[j]=temp;
                }
                i++;
            }
            j++;
        }

        //主要是不能包含基准值,不然会造成死循环
        _sortUp(arr,begin,i-2);
        _sortUp(arr,i,end);

        //第二种: i从前往后,j从后往前
        // int i=begin;
        // int j=end;
        //
        // while(i<j){
        //     if(arr[i]<=cur){
        //         i++;
        //     }else {
        //         if (arr[j] < cur) {
        //             int temp = arr[j];
        //             arr[j] = arr[i];
        //             arr[i] = temp;
        //             i++;
        //         }
        //         j--;
        //     }
        // }
        // arr[end]=arr[i];
        // arr[i]=cur;


        //主要是不能包含基准值,不然会造成死循环
        // _sortUp(arr,begin,i-1);
        // _sortUp(arr,i+1,end);

        return arr;
    }

    public static int[] sortDown(int[] arr){
        if(arr==null||arr.length<2){
            return arr;
        }
        _sortDown(arr,0,arr.length-1);
        return arr;
    }

    private static int[] _sortDown(int[] arr, int begin, int end){
        if(begin>=end){
            return arr;
        }

        int pivot=arr[end];

        int i = begin;
        int j = begin;

        while(j<=end){
            if(arr[j]>=pivot){
                if(i!=j){
                    int temp=arr[i];
                    arr[i]=arr[j];
                    arr[j]=temp;
                }
                i++;
            }
            j++;
        }

        _sortDown(arr,begin,i-2);
        _sortDown(arr,i,end);
        return arr;
    }

}
